{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Convert BST to Greater Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-search-tree #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉搜索树 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: convertBST"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #把二叉搜索树转换为累加树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给出二叉<strong> 搜索 </strong>树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 <code>node</code>&nbsp;的新值等于原树中大于或等于&nbsp;<code>node.val</code>&nbsp;的值之和。</p>\n",
    "\n",
    "<p>提醒一下，二叉搜索树满足下列约束条件：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>节点的左子树仅包含键<strong> 小于 </strong>节点键的节点。</li>\n",
    "\t<li>节点的右子树仅包含键<strong> 大于</strong> 节点键的节点。</li>\n",
    "\t<li>左右子树也必须是二叉搜索树。</li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>注意：</strong>本题和 1038:&nbsp;<a href=\"https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/\">https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/</a> 相同</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/05/03/tree.png\" style=\"height: 364px; width: 534px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]\n",
    "<strong>输出：</strong>[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>root = [0,null,1]\n",
    "<strong>输出：</strong>[1,null,1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>root = [1,0,2]\n",
    "<strong>输出：</strong>[3,3,2]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>root = [3,2,4,1]\n",
    "<strong>输出：</strong>[7,9,4,10]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中的节点数介于 <code>0</code>&nbsp;和 <code>10<sup>4</sup></code><sup>&nbsp;</sup>之间。</li>\n",
    "\t<li>每个节点的值介于 <code>-10<sup>4</sup></code>&nbsp;和&nbsp;<code>10<sup>4</sup></code>&nbsp;之间。</li>\n",
    "\t<li>树中的所有值 <strong>互不相同</strong> 。</li>\n",
    "\t<li>给定的树为二叉搜索树。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [convert-bst-to-greater-tree](https://leetcode.cn/problems/convert-bst-to-greater-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [convert-bst-to-greater-tree](https://leetcode.cn/problems/convert-bst-to-greater-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]', '[0,null,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.pre = 0\n",
    "\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root==None:\n",
    "            return None\n",
    "\n",
    "        self.convertBST(root.right) # 往右走到底\n",
    "        root.val = root.val + self.pre # 中节点计算\n",
    "        self.pre = root.val # 更新\n",
    "        self.convertBST(root.left) # 往左走到底\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        node_list = []\n",
    "        def helper(root):\n",
    "            if not root:\n",
    "                return \n",
    "            helper(root.right)\n",
    "            node_list.append(root.val)\n",
    "            temp_list = node_list[0:len(node_list)-1]\n",
    "            root.val += sum(temp_list)\n",
    "            \n",
    "            helper(root.left)\n",
    "        helper(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        from collections import defaultdict\n",
    "        self.d = defaultdict(TreeNode)\n",
    "        self.lst = []\n",
    "        def DFS(cur):\n",
    "            if cur is None:\n",
    "                return\n",
    "            self.d[cur.val] = cur\n",
    "            DFS(cur.left)\n",
    "            self.lst.append(cur.val)\n",
    "            DFS(cur.right)\n",
    "        \n",
    "        DFS(root)\n",
    "        temp = 0\n",
    "        n = len(self.lst)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            self.d[self.lst[i]].val += temp\n",
    "            temp += self.lst[i]\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        self.acc = 0\n",
    "\n",
    "        self.traverse(root)\n",
    "\n",
    "        return root\n",
    "\n",
    "\n",
    "    def traverse(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "\n",
    "        self.traverse(root.right)\n",
    "        self.acc += root.val\n",
    "        root.val = self.acc\n",
    "        self.traverse(root.left)\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        total = 0\n",
    "        p1 = root\n",
    "        while p1:\n",
    "            p2 = p1.right\n",
    "            if p2:\n",
    "                while p2.left and p2.left != p1:\n",
    "                    p2 = p2.left\n",
    "                if not p2.left:\n",
    "                    p2.left = p1\n",
    "                    p1 = p1.right\n",
    "                    continue\n",
    "                else:\n",
    "                    total += p1.val\n",
    "                    p1.val = total\n",
    "                    p2.left = None\n",
    "            else:\n",
    "                total += p1.val\n",
    "                p1.val = total\n",
    "            p1 = p1.left\n",
    "        return root\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    pre=0\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:  \n",
    "        if root is None:\n",
    "            return None\n",
    "        stack=[]\n",
    "        stack.append(root)\n",
    "        while len(stack) != 0:\n",
    "            cur=stack.pop()\n",
    "            if cur is not None:\n",
    "                if cur.left:\n",
    "                    stack.append(cur.left)\n",
    "                stack.append(cur)\n",
    "                stack.append(None)\n",
    "                if cur.right:\n",
    "                    stack.append(cur.right)\n",
    "            else:\n",
    "                cur=stack.pop()\n",
    "                self.pre+=cur.val\n",
    "                cur.val=self.pre\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        nodes = dict()\n",
    "        values = []\n",
    "        def inorder(root):\n",
    "            if not root:\n",
    "                return \n",
    "            inorder(root.left)\n",
    "            nodes[root.val] = root \n",
    "            values.append(root.val)\n",
    "            inorder(root.right)\n",
    "        inorder(root)\n",
    "        temp = 0\n",
    "        for i in range(len(values)-1,-1,-1):\n",
    "            if i == len(values)-1:\n",
    "                temp += values[i]\n",
    "            else:\n",
    "                temp += values[i]\n",
    "                nodes[values[i]].val = temp \n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        list_num = []\n",
    "        num_map = {}\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            list_num.append(node.val)\n",
    "            dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "        last_sum = 0\n",
    "        length = len(list_num)\n",
    "        for i in range(length - 1, -1, -1):\n",
    "            last_sum += list_num[i]\n",
    "            num_map[list_num[i]] = last_sum\n",
    "        print(num_map)\n",
    "        def dfs_sum(node):\n",
    "            if not node:\n",
    "                return\n",
    "            dfs_sum(node.left)\n",
    "            node.val = num_map[node.val]\n",
    "            dfs_sum(node.right)\n",
    "\n",
    "        dfs_sum(root)\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def dfs(self,root:TreeNode):\n",
    "        if not root:return \n",
    "        self.dfs(root.right)\n",
    "        self.pre_sum += root.val\n",
    "        root.val = self.pre_sum\n",
    "        self.dfs(root.left)\n",
    "\n",
    "\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        self.pre_sum = 0\n",
    "        self.dfs(root)\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        \"\"\"\n",
    "        二叉树的遍历\n",
    "        \"\"\"\n",
    "        self.s = 0\n",
    "        def dfs(root):\n",
    "            if root:\n",
    "                dfs(root.right)\n",
    "                self.s += root.val\n",
    "                root.val = self.s\n",
    "                dfs(root.left)\n",
    "            \n",
    "        dfs(root)\n",
    "        return root\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(root: TreeNode):\n",
    "            nonlocal total\n",
    "            if root:\n",
    "                dfs(root.right)\n",
    "                total += root.val\n",
    "                root.val = total\n",
    "                dfs(root.left)\n",
    "        \n",
    "        total = 0\n",
    "        dfs(root)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.sum = 0\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root==None:\n",
    "            return None\n",
    "        self.convertBST(root.right)\n",
    "        self.sum = self.sum + root.val\n",
    "        root.val = self.sum\n",
    "        self.convertBST(root.left)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(root):\n",
    "            nonlocal total\n",
    "            if root:\n",
    "                dfs(root.right)\n",
    "                total += root.val\n",
    "                root.val = total\n",
    "                dfs(root.left)\n",
    "        total = 0\n",
    "        dfs(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        # 反向的中序遍历, 传递累计值\n",
    "        # def loop(root, cursum):\n",
    "        #     if not root:\n",
    "        #         return cursum\n",
    "        #     right_sum = loop(root.right, cursum)\n",
    "        #     root.val = root.val + right_sum\n",
    "        #     left_sum = loop(root.left, root.val)\n",
    "        #     return left_sum\n",
    "\n",
    "        # loop(root, 0)\n",
    "        # return root\n",
    "\n",
    "        # 中序遍历迭代法\n",
    "        if not root:\n",
    "            return root\n",
    "        \n",
    "        stack = []\n",
    "        cursum = 0\n",
    "        node = root\n",
    "        while stack or root:\n",
    "            if root:\n",
    "                stack.append(root)\n",
    "                root = root.right\n",
    "            else:\n",
    "                root = stack.pop()\n",
    "                cursum += root.val\n",
    "                root.val = cursum\n",
    "                root = root.left\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(root):\n",
    "            nonlocal total\n",
    "            if root:\n",
    "                dfs(root.right)\n",
    "                total+=root.val\n",
    "                root.val=total\n",
    "                dfs(root.left)\n",
    "        total=0\n",
    "        dfs(root)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        self.reDFS(root)\n",
    "        return root\n",
    "\n",
    "    def reDFS(self, node):\n",
    "        if not node:\n",
    "            return None\n",
    "\n",
    "        self.reDFS(node.right)\n",
    "        self.res += node.val\n",
    "        node.val = self.res\n",
    "        self.reDFS(node.left)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.pre = 0\n",
    "\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        self.convertBST(root.right)\n",
    "        root.val += self.pre\n",
    "        self.pre = root.val\n",
    "        self.convertBST(root.left)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.sum = 0\n",
    "\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return root\n",
    "        self.convertBST(root.right)\n",
    "        root.val += self.sum\n",
    "        self.sum = root.val\n",
    "        self.convertBST(root.left)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.sums = 0\n",
    "        \n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        self.dfs(root)\n",
    "        return root\n",
    "\n",
    "    def dfs(self, root):\n",
    "        if not root:\n",
    "            return None\n",
    "        self.dfs(root.right)\n",
    "        self.sums += root.val   # 采用的是中序遍历反过来，把节点的值和大于节点的值都累加，赋给当前节点，妙！！\n",
    "        root.val = self.sums\n",
    "        self.dfs(root.left)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.pre = 0\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        self.pre = 0\n",
    "        self.travelsal(root)\n",
    "        return root\n",
    "    def travelsal(self,cur):\n",
    "        if not cur:\n",
    "            return\n",
    "        self.travelsal(cur.right)\n",
    "        cur.val += self.pre \n",
    "        self.pre = cur.val \n",
    "        self.travelsal(cur.left)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    # def __init__(self):\n",
    "    #     self.pre = 0\n",
    "    # def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "    #     self.pre = 0\n",
    "    #     self.traversal(root)\n",
    "    #     return root\n",
    "    # def traversal(self,cur):\n",
    "    #     if not cur:\n",
    "    #         return\n",
    "    #     self.traversal(cur.right)\n",
    "    #     cur.val += self.pre \n",
    "    #     self.pre = cur.val \n",
    "    #     self.traversal(cur.left)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.sum = 0\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        self.traverse(root)\n",
    "        return root\n",
    "\n",
    "    def traverse(self,root):\n",
    "        if not root:\n",
    "            return\n",
    "        self.traverse(root.right)\n",
    "        self.sum += root.val\n",
    "        root.val = self.sum\n",
    "        self.traverse(root.left)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        self.pre = 0  # 记录前一个节点的数值\n",
    "        self.traversal(root)\n",
    "        return root\n",
    "        \n",
    "    def traversal(self, cur):\n",
    "        if cur is None:\n",
    "            return        \n",
    "        self.traversal(cur.right)\n",
    "        cur.val += self.pre\n",
    "        self.pre = cur.val\n",
    "        self.traversal(cur.left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    pre=None\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        self.convertBST(root.right)\n",
    "        if self.pre:\n",
    "            root.val+=self.pre.val\n",
    "        self.pre=root\n",
    "        self.convertBST(root.left)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        self.nums = 0\n",
    "        def depthfirstsearch(root) :\n",
    "            if root is None :\n",
    "                return \n",
    "            else :\n",
    "                depthfirstsearch(root.right)\n",
    "                self.nums = self.nums + root.val \n",
    "                root.val = self.nums\n",
    "                depthfirstsearch(root.left)\n",
    "                return root\n",
    "        return depthfirstsearch(root)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def order(root, prex_sum = 0):\n",
    "            if not root:\n",
    "                return prex_sum\n",
    "            prex_sum = order(root.right, prex_sum)\n",
    "            root.val += prex_sum\n",
    "            prex_sum = root.val\n",
    "            prex_sum = order(root.left, prex_sum)\n",
    "            return prex_sum\n",
    "\n",
    "        order(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(root):\n",
    "            nonlocal total\n",
    "            if root:\n",
    "                dfs(root.right)\n",
    "                total += root.val\n",
    "                root.val = total\n",
    "                dfs(root.left)\n",
    "\n",
    "        total = 0\n",
    "        dfs(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        self.pre = 0\n",
    "        self.traversal(root)\n",
    "        return root\n",
    "    \n",
    "    def traversal(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        self.traversal(root.right)\n",
    "        root.val += self.pre\n",
    "        self.pre = root.val\n",
    "        self.traversal(root.left)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        sm=0\n",
    "        node=root\n",
    "        stack=[]\n",
    "        while stack or node:\n",
    "            while node:\n",
    "                stack.append(node)\n",
    "                node=node.right\n",
    "            node=stack.pop()    \n",
    "            sm+=node.val\n",
    "            node.val=sm\n",
    "            node=node.left\n",
    "        return root                        \n",
    "\n",
    "\n",
    "        # sm=0\n",
    "        # node=root\n",
    "        # stack=[]\n",
    "        # while stack or node:\n",
    "        #     while node:\n",
    "        #         stack.append(node)\n",
    "        #         node=node.right\n",
    "        #     node=stack.pop()\n",
    "        #     sm+=node.val\n",
    "        #     node.val=sm\n",
    "        #     node=node.left\n",
    "        # return root        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.sum = 0\n",
    "    def step(self, root):\n",
    "        if not root:\n",
    "            return root\n",
    "        root.right = self.step(root.right)\n",
    "        # print('传入和sum = {}'.format(sum))\n",
    "        self.sum += root.val\n",
    "        # print('与当前值：{}相加后sum = {}'.format(root.val,sum))\n",
    "        root.val = self.sum\n",
    "        root.left = self.step(root.left)\n",
    "        return root\n",
    "\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        return self.step(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    num = 0\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return root\n",
    "        self.convertBST(root.right)\n",
    "        root.val += self.num\n",
    "        self.num = root.val\n",
    "        self.convertBST(root.left)\n",
    "        return root\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        self.pre = 0\n",
    "        self.inorder(root)\n",
    "        return root\n",
    "    \n",
    "    def inorder(self, root):\n",
    "        if root == None: return\n",
    "        self.inorder(root.right)\n",
    "        root.val += self.pre\n",
    "        self.pre = root.val\n",
    "        self.inorder(root.left)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return root\n",
    "        cur=root\n",
    "        stack=[]\n",
    "        pre=0\n",
    "        while cur or stack:\n",
    "            if cur:\n",
    "                stack.append(cur)\n",
    "                cur=cur.right\n",
    "            else:\n",
    "                cur=stack.pop()\n",
    "                cur.val+=pre\n",
    "                pre=cur.val\n",
    "                cur=cur.left\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.pre=0\n",
    "    def zhuanhuan(self,cur):\n",
    "        if cur==None:\n",
    "            return \n",
    "        self.zhuanhuan(cur.right)\n",
    "        cur.val+=self.pre\n",
    "        self.pre=cur.val\n",
    "        self.zhuanhuan(cur.left)\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        self.zhuanhuan(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        res = 0\n",
    "        def dfs(node, res):\n",
    "            if node:\n",
    "                if node.right:\n",
    "                    res = dfs(node.right, res)\n",
    "                res += node.val\n",
    "                node.val = res\n",
    "                if node.left:\n",
    "                    res = dfs(node.left, res)\n",
    "            return res\n",
    "        dfs(root, res)\n",
    "        return root\n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.pre=0\n",
    "    def traversal(self,cur):\n",
    "        if cur is None:\n",
    "            return \n",
    "        self.traversal(cur.right)\n",
    "        cur.val+=self.pre\n",
    "        self.pre=cur.val\n",
    "        self.traversal(cur.left)\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        self.traversal(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        # 逆序\n",
    "        def run(node):\n",
    "            nonlocal total\n",
    "            if node:\n",
    "                run(node.right)\n",
    "                total += node.val\n",
    "                node.val = total\n",
    "                run(node.left)\n",
    "        total = 0\n",
    "        run(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        cursum = 0\n",
    "        def backorder(root):\n",
    "            if not root:\n",
    "                return\n",
    "            backorder(root.right)\n",
    "\n",
    "            nonlocal cursum\n",
    "            cursum += root.val\n",
    "            root.val = cursum\n",
    "\n",
    "            backorder(root.left)\n",
    "            return\n",
    "        backorder(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.pre = 0\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        self.traversal(root)\n",
    "        return root\n",
    "    def traversal(self, cur):\n",
    "        if cur is None:\n",
    "            return        \n",
    "        self.traversal(cur.right)\n",
    "        cur.val += self.pre\n",
    "        self.pre = cur.val\n",
    "        self.traversal(cur.left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self,root):\n",
    "        if(root == None):\n",
    "            return root\n",
    "        root.right = self.dfs(root.right)\n",
    "        root.val = self.cum_sum + root.val\n",
    "        self.cum_sum = root.val\n",
    "        root.left = self.dfs(root.left)\n",
    "        return root\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        self.cum_sum=0\n",
    "        return self.dfs(root)\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        self.sum = 0\n",
    "        self.traverse(root)\n",
    "        return root\n",
    "    def traverse(self, root):\n",
    "        if root is None:\n",
    "            return None\n",
    "        \n",
    "        self.traverse(root.right)\n",
    "        self.sum += root.val\n",
    "        root.val = self.sum\n",
    "        self.traverse(root.left)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(root):\n",
    "            nonlocal total\n",
    "            if root is None:\n",
    "                return 0\n",
    "            \n",
    "            dfs(root.right)       \n",
    "            total += root.val\n",
    "            root.val = total\n",
    "            dfs(root.left)\n",
    "\n",
    "        total = 0\n",
    "        dfs(root)\n",
    "        return root\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        nodes = list()\n",
    "        self.inorder(root, nodes)\n",
    "        sum_node = 0\n",
    "        for node in nodes[::-1]:\n",
    "            val = node.val\n",
    "            node.val += sum_node\n",
    "            sum_node += val\n",
    "        return root\n",
    "    \n",
    "    def inorder(self, root, nodes):\n",
    "        if root is None: return\n",
    "        self.inorder(root.left, nodes)\n",
    "        nodes.append(root)\n",
    "        self.inorder(root.right, nodes)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(root: TreeNode):\n",
    "            nonlocal total\n",
    "            if root:\n",
    "                dfs(root.right)\n",
    "                total += root.val\n",
    "                root.val = total\n",
    "                dfs(root.left)\n",
    "        \n",
    "        total = 0\n",
    "        dfs(root)\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        \n",
    "        stack = []\n",
    "        pre = TreeNode(0)\n",
    "        cur = root\n",
    "        while cur or stack:\n",
    "            if cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.right\n",
    "            else:\n",
    "                cur = stack.pop()\n",
    "                if pre:\n",
    "                    cur.val += pre.val\n",
    "                \n",
    "                pre = cur\n",
    "                cur = cur.left\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    total_num = 0\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return\n",
    "        \n",
    "        self.convertBST(root.right)\n",
    "        self.total_num += root.val\n",
    "        root.val = self.total_num\n",
    "        self.convertBST(root.left)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        cur=root\n",
    "        stack=[]\n",
    "        pre=None\n",
    "        while cur or stack:\n",
    "            if cur:\n",
    "                stack.append(cur)\n",
    "                cur=cur.right\n",
    "            else:\n",
    "                cur=stack.pop()\n",
    "                if pre:\n",
    "                    cur.val+=pre.val\n",
    "                pre=cur\n",
    "                cur=cur.left\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "\n",
    "        def traverse(node):\n",
    "            nonlocal cur_val\n",
    "            if not node:\n",
    "                return None\n",
    "            \n",
    "            traverse(node.right)\n",
    "            cur_val = node.val + cur_val\n",
    "            node.val = cur_val\n",
    "            traverse(node.left)\n",
    "\n",
    "            return node\n",
    "\n",
    "        \n",
    "        cur_val = 0\n",
    "        res = traverse(root)\n",
    "\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # def traverse(root):\n",
    "        #     nonlocal cur_sum\n",
    "        #     if not root:\n",
    "        #         return None\n",
    "\n",
    "        #     # right\n",
    "        #     traverse(root.right)\n",
    "\n",
    "        #     # middle\n",
    "        #     cur_sum = root.val + cur_sum\n",
    "        #     root.val = cur_sum\n",
    "            \n",
    "        #     # left\n",
    "        #     traverse(root.left)\n",
    "\n",
    "        #     return root\n",
    "        \n",
    "        # cur_sum = 0\n",
    "        # res = traverse(root)\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def traverse(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            traverse(root.right)\n",
    "            self.res += root.val\n",
    "            root.val = self.res\n",
    "            traverse(root.left)\n",
    "        traverse(root)\n",
    "        return root\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self,root):\n",
    "        if(root == None):\n",
    "            return None\n",
    "        right = self.dfs(root.right)\n",
    "        self.cum_sum += root.val\n",
    "        root.val = self.cum_sum\n",
    "        if(root.left != None):\n",
    "            left = self.dfs(root.left)\n",
    "        return root\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        self.cum_sum=0\n",
    "        return self.dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        cumu_sum = 0\n",
    "\n",
    "        def dfs(root):\n",
    "            if root is None: return\n",
    "            dfs(root.right)\n",
    "            nonlocal cumu_sum\n",
    "            cumu_sum += root.val\n",
    "            root.val = cumu_sum\n",
    "            dfs(root.left)\n",
    "        \n",
    "        dfs(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def run(node):\n",
    "            nonlocal total\n",
    "            if node:\n",
    "                run(node.right)\n",
    "                total += node.val\n",
    "                node.val = total\n",
    "                run(node.left)\n",
    "        total = 0\n",
    "        run(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.count = 0\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        self.tranverse(root)\n",
    "        return root\n",
    "\n",
    "    def tranverse(self, root):\n",
    "        if root == None:\n",
    "            return None\n",
    "        self.tranverse(root.right)\n",
    "        root.val += self.count\n",
    "        self.count = root.val\n",
    "        self.tranverse(root.left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return\n",
    "        self.s = 0\n",
    "        self.tree(root)\n",
    "        return root\n",
    "    def tree(self,root):    \n",
    "        if not root:\n",
    "            return \n",
    "        root.right = self.tree(root.right)\n",
    "        root.val += self.s\n",
    "        self.s = root.val \n",
    "        root.left = self.tree(root.left)\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(root: TreeNode):\n",
    "            nonlocal total\n",
    "            if root:\n",
    "                dfs(root.right)\n",
    "                total += root.val\n",
    "                root.val = total\n",
    "                dfs(root.left)\n",
    "        \n",
    "        total = 0\n",
    "        dfs(root)\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        self.pre=0\n",
    "        self.traval(root)\n",
    "        return root\n",
    "    \n",
    "    def traval(self,root):\n",
    "        if not root:\n",
    "            return\n",
    "        \n",
    "        self.traval(root.right)\n",
    "        root.val+=self.pre\n",
    "        self.pre=root.val\n",
    "        self.traval(root.left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        val_sum = [0]\n",
    "        \n",
    "        def tra(root):\n",
    "            if not root:\n",
    "                return\n",
    "            \n",
    "            tra(root.right)\n",
    "            val_sum[0] += root.val\n",
    "            root.val = val_sum[0]\n",
    "            tra(root.left)\n",
    "        \n",
    "        tra(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(root) -> int:\n",
    "            nonlocal total\n",
    "            if root is None:\n",
    "                return 0\n",
    "            \n",
    "            dfs(root.right)       \n",
    "            total += root.val\n",
    "            root.val = total\n",
    "            dfs(root.left)\n",
    "\n",
    "        total = 0\n",
    "        dfs(root)\n",
    "        return root\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        stack=[]\n",
    "        preSum=0\n",
    "        cur=root\n",
    "        while cur or stack:\n",
    "            if cur:\n",
    "                stack.append(cur)\n",
    "                cur=cur.right\n",
    "            else:\n",
    "                cur=stack.pop()\n",
    "                cur.val+=preSum\n",
    "                preSum=cur.val\n",
    "                cur=cur.left\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        preSum=0\n",
    "        def nodeSum(root:TreeNode):\n",
    "            if not root:\n",
    "                return None\n",
    "            nodeSum(root.right)\n",
    "            nonlocal preSum\n",
    "            root.val+=preSum\n",
    "            preSum=root.val\n",
    "            nodeSum(root.left)\n",
    "        nodeSum(root)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        self.ans=0\n",
    "        def dfs(root):\n",
    "            if not root:return\n",
    "            dfs(root.right)\n",
    "            self.ans+=root.val\n",
    "            root.val=self.ans\n",
    "            dfs(root.left)\n",
    "        dfs(root)\n",
    "        return root\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def traversal(self, root: Optional[TreeNode]):\n",
    "        if not root:\n",
    "            return None\n",
    "        self.traversal(root.right) # 右\n",
    "        root.val += self.pre\n",
    "        self.pre = root.val\n",
    "        self.traversal(root.left) # 左\n",
    "\n",
    "        return root\n",
    "\n",
    "\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        self.pre = 0\n",
    "        return self.traversal(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.pre = 0 # 全局变量，存放前一个节点的值，一开始在空节点，初始化为0\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return None\n",
    "        # 右\n",
    "        self.convertBST(root.right)\n",
    "        # 中\n",
    "        root.val += self.pre\n",
    "        self.pre = root.val\n",
    "        # 左\n",
    "        self.convertBST(root.left)\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        self.num = 0\n",
    "        def traverse(root):\n",
    "            if not root:\n",
    "                return\n",
    "            traverse(root.right)\n",
    "            self.num += root.val\n",
    "            root.val = self.num\n",
    "            traverse(root.left)\n",
    "\n",
    "        traverse(root)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.count = 0\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        self.tranverse(root)\n",
    "        return root\n",
    "\n",
    "    def tranverse(self, root):\n",
    "        if root == None:\n",
    "            return None\n",
    "        self.tranverse(root.right)\n",
    "        self.count += root.val\n",
    "        root.val = self.count\n",
    "        self.tranverse(root.left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "# 反中序遍历，记录前一个结点pre，当前结点的累加等于当前结点值加上pre的值\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        self.pre = 0\n",
    "        self.traversal(root)\n",
    "        return root\n",
    "\n",
    "\n",
    "    def traversal(self, cur):\n",
    "        if not cur:\n",
    "            return\n",
    "\n",
    "        self.traversal(cur.right)\n",
    "        cur.val += self.pre\n",
    "        self.pre = cur.val\n",
    "        self.traversal(cur.left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.s = 0\n",
    "\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "\n",
    "        def traverse(node):\n",
    "\n",
    "            if not node:\n",
    "                return\n",
    "\n",
    "            traverse(node.right)\n",
    "            self.s += node.val\n",
    "            node.val = self.s\n",
    "            traverse(node.left)\n",
    "\n",
    "        traverse(root)\n",
    "        return root\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def search(root, num):\n",
    "            if root.right:\n",
    "                num = search(root.right, num)\n",
    "            num+=root.val\n",
    "            root.val=num\n",
    "            if root.left:\n",
    "                num = search(root.left, num)\n",
    "            return num\n",
    "        if root:search(root, 0)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(root:TreeNode,total):\n",
    "            if root is None:\n",
    "                return total\n",
    "            root.val+=dfs(root.right,total)\n",
    "            return dfs(root.left,root.val)\n",
    "        dfs(root,0)\n",
    "        return root\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    total = 0\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        \n",
    "        def dfs(root):\n",
    "            if root:\n",
    "                nonlocal total\n",
    "                dfs(root.right)\n",
    "                total += root.val\n",
    "                root.val = total\n",
    "                dfs(root.left)\n",
    "        total = 0\n",
    "        dfs(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def traverse(self, root):\n",
    "        if root is None:\n",
    "            return None\n",
    "        self.traverse(root.right)\n",
    "        print(root.val)\n",
    "        self.sum += root.val\n",
    "        cur_val = self.sum\n",
    "        self.traverse(root.left)\n",
    "        root.val = cur_val\n",
    "\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        self.sum = 0\n",
    "        self.traverse(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def traverse(root):\n",
    "            nonlocal cur_sum\n",
    "            if not root:\n",
    "                return None\n",
    "            \n",
    "            traverse(root.right)\n",
    "            cur_sum = root.val + cur_sum\n",
    "            root.val = cur_sum\n",
    "            traverse(root.left)\n",
    "\n",
    "            return root\n",
    "        \n",
    "        cur_sum = 0\n",
    "        res = traverse(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def traversal(root,nums):\n",
    "            if not root:\n",
    "                return None\n",
    "            traversal(root.right,nums)\n",
    "            nums.append(root.val)\n",
    "            root.val = sum(nums)\n",
    "            traversal(root.left,nums)\n",
    "            return root\n",
    "        nums = []\n",
    "        return traversal(root,nums)\n",
    "        \n",
    "        # if not root:\n",
    "        #     return \n",
    "        # stack = []\n",
    "        # cur = root\n",
    "        # num = 0\n",
    "        # while cur or stack:\n",
    "        #     if cur:\n",
    "        #         stack.append(cur)\n",
    "        #         cur = cur.right\n",
    "        #     else:\n",
    "        #         cur = stack.pop()\n",
    "        #         cur.val += num\n",
    "        #         num = cur.val\n",
    "        #         cur = cur.left\n",
    "        # return root\n",
    "  \n",
    "  \n",
    "        # pre = 0\n",
    "        # def traversal(node):\n",
    "        #     nonlocal pre\n",
    "        #     if not node:\n",
    "        #         return \n",
    "        #     traversal(node.right)\n",
    "        #     node.val += pre\n",
    "        #     pre = node.val\n",
    "        #     traversal(node.left)\n",
    "        #     return node\n",
    "        # return traversal(root)\n",
    "\n",
    "\n",
    "        # result = []\n",
    "        # def DFS(node):\n",
    "        #     if not node:\n",
    "        #         return \n",
    "        #     DFS(node.right)\n",
    "        #     result.append(node.val)\n",
    "        #     DFS(node.left)\n",
    "        #     return result\n",
    "        # DFS(root)\n",
    "        # for i in range(1,len(result)):\n",
    "        #     result[i] += result[i-1]\n",
    "        # def traversal(node):\n",
    "        #     if not node:\n",
    "        #         return \n",
    "        #     traversal(node.right)\n",
    "        #     node.val = result.pop(0)\n",
    "        #     traversal(node.left)\n",
    "        # traversal(root)\n",
    "        # return root\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def reverseInorder(node):\n",
    "            if not node: return\n",
    "            reverseInorder(node.right)\n",
    "            nonlocal pre\n",
    "            node.val += pre\n",
    "            pre = node.val\n",
    "            reverseInorder(node.left)\n",
    "\n",
    "        pre = 0\n",
    "        reverseInorder(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        num = 0\n",
    "        def recur(root):\n",
    "            nonlocal num\n",
    "            if not root: return\n",
    "\n",
    "            recur(root.right)\n",
    "            num += root.val\n",
    "            root.val = num\n",
    "            recur(root.left)\n",
    "        recur(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        post=0\n",
    "        def func(root):\n",
    "            nonlocal post\n",
    "            if not root:\n",
    "                None\n",
    "            else:\n",
    "                func(root.right)\n",
    "                post+=root.val\n",
    "                root.val=post\n",
    "                func(root.left)\n",
    "        func(root)\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    cur_sum = 0\r\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\r\n",
    "        if not root: return root\r\n",
    "        self.convertBST(root=root.right)\r\n",
    "        root.val = root.val + self.cur_sum\r\n",
    "        self.cur_sum = root.val\r\n",
    "        self.convertBST(root=root.left)\r\n",
    "        return root\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sums(self, root, num):\n",
    "        if not root:\n",
    "            return\n",
    "\n",
    "        if root.right:\n",
    "            self.sums(root.right, num)\n",
    "        \n",
    "        sum_num = 0\n",
    "        num.append(root.val)\n",
    "        for i in range(len(num)):\n",
    "            sum_num += num[i]\n",
    "        root.val = sum_num\n",
    "\n",
    "        if root.left:\n",
    "            self.sums(root.left, num)\n",
    "\n",
    "        \n",
    "\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        temp = root\n",
    "        num = []\n",
    "        self.sums(root, num)\n",
    "\n",
    "        return temp\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    pre = 0\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(node):\n",
    "            if not node: return None\n",
    "            dfs(node.right)\n",
    "            node.val += self.pre\n",
    "            self.pre = node.val\n",
    "            dfs(node.left)\n",
    "            return node\n",
    "        return dfs(root)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
